//
//  ProblemOffer48.swift
//  TestProject
//
//  Created by 武侠 on 2022/3/8.
//  Copyright © 2022 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 48. 最长不含重复字符的子字符串 ✅
 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

 示例 1:
     输入: "abcabcbb"
     输出: 3
     解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 示例 2:
     输入: "bbbbb"
     输出: 1
     解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 示例 3:
     输入: "pwwkew"
     输出: 3
     解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 提示：
 s.length <= 40000
 */
class ProblemOffer48: NSObject {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        if s.count <= 1 {
            return s.count
        }
        
        var start: Int = 0, max: Int = 1
        for ci in (1..<s.count) {
            for bi in start..<ci {
                if s[s.index(s.startIndex, offsetBy: bi)] == s[s.index(s.startIndex, offsetBy: ci)] {
                    if ci - start > max {
                        max = ci - start
                    }
                    start = bi+1
                    break
                }
            }
        }
        
        return s.count - start > max ? s.count - start : max
    }
}
